The Colouring problem asks whether the vertices of a graph can be colouredwith at most $k$ colours for a given integer $k$ in such a way that no twoadjacent vertices receive the same colour. A graph is $(H_1,H_2)$-free if ithas no induced subgraph isomorphic to $H_1$ or $H_2$. A connected graph $H_1$is almost classified if Colouring on $(H_1,H_2)$-free graphs is known to bepolynomial-time solvable or NP-complete for all but finitely many connectedgraphs $H_2$. We show that every connected graph $H_1$ apart from the claw$K_{1,3}$ and the $5$-vertex path $P_5$ is almost classified. We also prove anumber of new hardness results for Colouring on $(2P_2,H)$-free graphs. Thisenables us to list all graphs $H$ for which the complexity of Colouring is openon $(2P_2,H)$-free graphs and all graphs $H$ for which the complexity ofColouring is open on $(P_5,H)$-free graphs. In fact we show that these twolists coincide. Moreover, we show that the complexities of Colouring for$(2P_2,H)$-free graphs and for $(P_5,H)$-free graphs are the same for all knowncases.
展开▼
机译：着色问题询问对于给定的整数$ k $，图的顶点是否最多可以用$ k $种颜色进行着色，以使两个相邻的顶点都不接收相同的颜色。如果没有诱导子图与$ H_1 $或$ H_2 $同构的图，则该图无$（H_1，H_2）$。如果已知无（$ H_1，H_2）$图上的着色对于除有限数量的所有连接图$ H_2 $之外的所有图都是多项式时间可解的或NP完全的，则对连通图$ H_1 $几乎进行了分类。我们显示，除了爪$ K_ {1,3} $和$ 5 $-顶点路径$ P_5 $之外，每个连通图$ H_1 $几乎都被分类了。我们还在无（$ 2P_2，H）$图表上证明了着色的许多新硬度结果。这使我们能够列出所有着色不需$ {2P_2，H）$的图$ H $，且着色不需打开$（P_5，H）$的图$ H $图。实际上，我们表明这两个列表是重合的。而且，我们表明，对于所有已知情况，无（$ 2P_2，H）$无图和无（$ P_5，H）$图的着色的复杂性都相同。
展开▼
